class Solution09 {

    public static void main(String[] args) {
     int[][] arr =
             {{1,4,7,11,15},{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30}};
        System.out.println(searchMatrix(arr, 5));
    }
    public static boolean searchMatrix(int[][] matrix, int target) {

          int n = matrix.length ;
          if(n==0) return false ;
          int m = matrix[0].length ;
          for(int i = 0 ; i < n ; i ++){
               int left = 0 , right = m-1 ;

               while(left <= right){
               int mid = left + (right-left)/2 ;
                if(matrix[i][mid] > target){
                        right  = mid -1 ;
                }else if(matrix[i][mid] < target){
                   left  = mid +1 ;
                }else{
                    return true ;
                }
               }

          }
           return false ;

    }
}